|
In graph theory, Schnyder's theorem is a characterization of planar graphs in terms of the order dimension of their incidence posets. It is named after Walter Schnyder, who published its proof in . The incidence poset of an undirected graph with vertex set and edge set is the partially ordered set of height 2 that has as its elements. In this partial order, there is an order relation when is a vertex, is an edge, and is one of the two endpoints of . The order dimension of a partial order is the smallest number of total orderings whose intersection is the given partial order; such a set of orderings is called a ''realizer'' of the partial order. Schnyder's theorem states that a graph is planar if and only if the order dimension of is at most three. == Extensions == This theorem has been generalized by to a tight bound on the dimension of the height-three partially ordered sets formed analogously from the vertices, edges and faces of a convex polyhedron, or more generally of an embedded planar graph: in both cases, the order dimension of the poset is at most four. However, this result cannot be generalized to higher-dimensional convex polytopes, as there exist four-dimensional polytopes whose face lattices have unbounded order dimension. Even more generally, for abstract simplicial complexes, the order dimension of the face poset of the complex is at most , where is the minimum dimension of a Euclidean space in which the complex has a geometric realization . 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Schnyder's theorem」の詳細全文を読む スポンサード リンク
|